#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: one_zero_package.py 
@version:
@time: 2023/12/20


首先要考虑该问题采用动态规划算法是否合适，根据3.1.1小节的动态规划四要素来寻找该题
目是否有最优子结构、是否有重叠子问题。要想获得原始问题的最优策略，那么必须找到规模更小
的子问题的最优解决策略。

通过将子问题的最优解结合得到原始问题的最优解。要想知道如何在满足最大容量的情况下
在n个物品中做选择，使背包所容纳的价值最大，就需要一件一件物品考虑，容量一步一步扩大，
考虑每一件物品在每种容量的情况下是否要放入，而子问题与子问题之间的解决思路都是相同的，
因此该问题满足最优子结构和重叠子问题的条件。

接下来找状态和状态转移方程，在做每一步判断时，我们都想知道是否将这个物品放入背包，放入
背包之后会比不放入价值更高吗？那么我们就需要知道在当前所能容纳的质量下，如果不放入该物品，
价值多少；如果放入该物品，价值多少。二者进行比较，得出结论，是否放入该物品。因此，我们需要
一个二维空爱你来保存考虑前i件物品时，背包最大容量为j时，背包中的最大价值是多少。

最后找约束条件，约束条件很明显就是背包所能承受的最大质量。如果物品质量超过背包所
能承受的最大质量，那么该物品就无须考虑了，必然不能让如

找到原始问题的四要素后，说明该问题用动态规划算法可以得到较好的解决。

定义一个二维数组来保存当前背包容量j，前i个物品最佳组合对应的价值

i/j|0|1|2|3|4|5|
0   0 0 0 0 0 0
1   0 0 0 0 0 0
2   0 0 0 0 0 0
3   0 0 0 0 0 0
4   0 0 0 0 0 max

"""


def bag(weight, value, max_weight):
    """

    :param weight:  物品重量
    :param value:  物品价值
    :param max_weight:  最大重量
    :return:
    """
    weight.insert(0, 0)
    value.insert(0, 0)
    # weight [1,3,2,4] -> [0,1,3,2,4]
    # value [200, 240, 140, 150] -> [0, 200, 240, 140, 150]

    thing_num = len(weight)
    # 获取物品数量 4, 但是从0取到4， 0 1 2 3 4

    dp = []
    # 结果列表
    for i in range(thing_num):
        dp.append([0] * (max_weight + 1))
    # 用0填充结果列表,4个物品，最大质量为5，
    # 所以从0到4取出物品，边界是5
    # 最大质量是从0到5，边界是6，也就是max_weight+1
    """
        i/j|0|1|2|3|4|5|
        0   0 0 0 0 0 0
        1   0 0 0 0 0 0
        2   0 0 0 0 0 0
        3   0 0 0 0 0 0
        4   0 0 0 0 0 max
    """
    # thing_num 物品数量
    # max_weight 最大重量
    # weight 物品重量
    # value 物品价值
    for i in range(1, thing_num):
        # 依次从物品种取出
        for j in range(1, max_weight + 1):
            # 第一次dp[0][0] = 0
            dp[i][j] = dp[i - 1][j]
            # dp[i][j]等于上轮放置的位置的价值
            if j >= weight[i]:
                dp[i][j] = max(
                    dp[i - 1][j],
                    dp[i - 1][j - weight[i]] + value[i]
                )
            print(dp)
    """
    i    j     dp[1][1]    weight[1]
    1    1     0           1
    dp[1][1] = max(dp[1-1][1],dp[0][1-1]+value[1])
    dp[1][1] = max(0,0+200)
    
    
    1    2     dp[1][2]    weight[1]
               0           1
    dp[1][2] = max(dp[1-1][2],dp[0][2-1]+value[1])
    dp[1][1] = max(0,0+200)
    ...
    
    2    1    dp[2][1]    weight[2]
              0           3
    dp[2][1] = dp[1][1] = 200
    ...
    
    2    3    dp[2][3]    weight[2]
              200         3
    dp[2][3] = max(dp[1][3],dp[1][3-3]+value[2])
    dp[2][3] = max(200, 0+24o)
                                     
    2    4    dp[2][4]    weight[2]
              200         3
    dp[2][4] = max(dp[1][4],dp[1][1]+value[2])
    dp[2][4] = max(200, 200+240)                                     
    """
    # return dp[5-1][5]
    return dp[thing_num - 1][max_weight]


res = bag([1, 3, 2, 4], [200, 240, 140, 150], 5)
print(res)
